package com.leetcode.array_link;


import com.leetcode.TreeNode;

public class Leetcode98 {

    /*
    solution 1:
        给左右子节点一个数值范围：
        左节点：from min to current value, 如果min 是null，左节点不存在，就不需要比较
        右节点：from current value to max，如果max 是null，右节点不存在，就不需要比较
        public static boolean isValidBST(TreeNode root) {
            return isValidBST(root,null,null);
        }


        private static boolean isValidBST(TreeNode root,Integer min,Integer max) {
            if(root == null){
                return true;
            }

            if((min!= null  && min >= root.val) ||
                    (max != null && max <= root.val)){
                return false;
            }

            return isValidBST(root.left,min,root.val) && isValidBST(root.right,root.val,max);
        }
    */
    private static Integer prev;
    public static boolean isValidBST(TreeNode root) {
        if(root == null){
            return true;
        }

        if(!isValidBST(root.left)){
            return false;
        }

        if(prev != null && prev >= root.val){
            return false;
        }

        prev = root.val;
        return isValidBST(root.right);
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(2);
        TreeNode left = new TreeNode(1);
        TreeNode right = new TreeNode(3);
        root.left = left;
        root.right = right;

        System.out.println(isValidBST(root));
    }
}
